package history

type TreeNodeX struct {
	val   int
	left  *TreeNodeX
	right *TreeNodeX
}

// 先序遍历 中左右
func preSearchTreeNodeX(root *TreeNodeX) []int {
	var res []int

	var dfs func(node *TreeNodeX)
	dfs = func(node *TreeNodeX) {
		if node == nil {
			return
		}
		res = append(res, node.val)
		dfs(node.left)
		dfs(node.right)
	}
	return res
}

func preSearchTreeNodeXStack(root *TreeNodeX) []int {
	var stack = []*TreeNodeX{root}
	var res []int
	for len(stack) > 0 {
		curNode := stack[0]
		stack = stack[1:]
		for curNode != nil {
			res = append(res, curNode.val)
			if curNode.right != nil {
				stack = append([]*TreeNodeX{curNode.right}, stack...)
			}
			if curNode.left != nil {
				stack = append([]*TreeNodeX{curNode.left}, stack...)
			}
		}
	}
	return res
}

type LinkedNode struct {
	val  int
	next *LinkedNode
}

func reverseLinkedNode(head *LinkedNode) *LinkedNode {
	if head == nil || head.next == nil {
		return head
	}
	var curNode = head
	var preNode *LinkedNode
	var next = head.next
	for curNode.next != nil {
		curNode.next = preNode

		var tmpNext = next.next
		next.next = curNode
		preNode = curNode
		curNode = next

		next = tmpNext
	}

	return curNode
}
